package cn.lishiyuan.algorithm.search;


import java.util.List;

/**
 * 二分查找
 * <br>
 * 从小于目标元素则向前查找，如果大于目标元素则向后查找，如何等于则直接返回。
 *
 */
public class BinarySearch implements LeeSearch {

    @Override
    public <T extends Comparable<T>> int search(List<T> arr, T target) {
        int size = arr.size();
        int i = binarySearch(arr, target, 0, size - 1);
        return i;
    }

    private <T extends Comparable<T>> int binarySearch(List<T> arr, T target, int low, int high){

        if(low > high){
            return -1;
        }
        // 取中
        int mid = (low + high)/2;
        if(arr.get(mid).compareTo(target) == 0){
            return mid;
        }
        if(arr.get(mid).compareTo(target) < 0){
            return binarySearch(arr, target, mid + 1,high);
        }
        return binarySearch(arr, target, low, mid - 1);
    }

    @Override
    public <T extends Comparable<T>> int search(T[] arr, T target) {
        int i = binarySearch(arr, target, 0, arr.length - 1);
        return i;
    }

    private <T extends Comparable<T>> int binarySearch(T[] arr, T target, int low, int high){
        // 取中
        if(low > high){
            return - 1;
        }
//        int mid = (low + high)/2;
        // 防止int溢出的，(high - low) >> 1相当于给high和low的差值除以2
        int mid = low + ((high - low) >> 1);
        for(; low <= high; ){
            if(arr[mid].compareTo(target) == 0){
                return mid;
            }
            if(arr[mid].compareTo(target) < 0){
                // 右边查找
                low = mid + 1;
            }else {
                high = mid - 1;
            }
            mid = low + ((high - low) >> 1);
        }
        return -1;
    }
}
